package com.vint.mi;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 1. done,easy
 * 2. BFS
 * 求有几个岛
 */
public class Mi55 {

    public static String solution(String line){
        String[] src = line.split(" ");
        int w = src.length;
        int h = src[0].split(",").length;
        char[][] ret = new char[w][h];
        for(int i = 0; i < w; i++){
            String[] s = src[i].split(",");
            for(int j=0;j<h;j++){
                if(s[j].equals("1")){
                    ret[i][j] = '1';
                }else{
                    ret[i][j] = '0';
                }
            }
        }

        return island(ret,w,h)+"";
    }

    public static int island(char[][] ret, int w, int h){
        boolean[][] src = new boolean[w][h];
        for(int i = 0; i < w; i++){
            for(int j = 0; j < h; j++) {
                src[i][j] = false;
            }
        }
        int count = 0;
        for(int i = 0; i < w; i++){
            for(int j = 0; j < h; j++) {
                if(ret[i][j]=='0')continue;
                if(src[i][j])continue;
                count++;
                src[i][j] = true;
                Queue<Point> queue = new LinkedList<>();
                queue.add(new Point(i,j));
                while (!queue.isEmpty()){
                   Point point = queue.poll();
                   src[point.x][point.y] = true;
                   if(point.x-1>=0&&ret[point.x-1][point.y]=='1'&&src[point.x-1][ point.y]==false){
                        src[point.x-1][point.y] = true;
                        queue.add(new Point(point.x-1,point.y));
                    }
                    if(point.x+1<w&&ret[point.x+1][point.y]=='1'&&src[point.x+1][ point.y]==false){
                        src[point.x+1][point.y] = true;
                        queue.add(new Point(point.x+1,point.y));
                    }
                    if(point.y-1>=0&&ret[point.x][point.y-1]=='1'&&src[point.x][ point.y-1]==false){
                        src[point.x][point.y-1] = true;
                        queue.add(new Point(point.x,point.y-1));
                    }
                    if(point.y+1<h&&ret[point.x][point.y+1]=='1'&&src[point.x][ point.y+1]==false){
                        src[point.x][point.y+1] = true;
                        queue.add(new Point(point.x,point.y+1));
                    }
                }
            }
        }
        return count;
    }
    static class Point{
        int x;
        int y;
        public Point(int xx, int yy){
            x = xx;
            y = yy;
        }
    }
    public static void main(String[] args) {
        char[][] src = {{'1','0','1'},{'0','1','1'}};
        String s1 = "1,1,1,1,0 1,1,0,1,0 1,1,0,0,0 0,0,0,0,0";
        String s2 = "1,1,0,0,0 1,1,0,0,0 0,0,1,0,0 0,0,0,1,1";
        System.out.println(island(src,2,3));
        System.out.println(solution(s1));
        System.out.println(solution(s2));
    }
}
